package Year22_Month07.day07;

public class 快排 {
    public int[] sortArray(int[] nums) {
        quickSort(nums,0,nums.length);
        return nums;
    }

    public void quickSort(int[] nums,int begin,int end){
        if(end - begin > 1){
            int index = partion(nums,begin,nums.length);
            quickSort(nums,begin,index);
            quickSort(nums,index + 1,end);
        }
    }

    public int partion(int[] nums,int left,int right){
        int key = nums[right];
        int begin = left;
        int end = right;
        while(begin < end){
            while(begin < end && nums[begin] <= key){
                begin++;
            }
            while(begin < end && nums[end] >= key){
                end--;
            }
            if(begin < end) {
                swap(nums, begin, end);
            }
        }
        swap(nums,begin,right-1);
        return begin;
    }

    public void swap(int[] nums,int i,int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}
